#include "Graph.h"
class DijkstraAlgo{
private:
    int start_vertex;
    std::vector<int> distances;
    std::vector<int> parent;
    Graph& graph;
    std::vector<bool> used;
    void PerformRelaxation(int vertex){
        used[vertex] = true;
        std::vector<edge> incident_list = graph.GetIncidentEdges(vertex);
        for(int incident_edge = 0; incident_edge < incident_list.size(); incident_edge++){
            int incident_vertex = incident_list[incident_edge].to;
            int weight = incident_list[incident_edge].weight;
            if(distances[vertex] + weight < distances[incident_vertex]){
                distances[incident_vertex] = distances[vertex] + weight;
                parent[incident_vertex] = vertex;
            }
        }
    }
    
    void LaunchAlgorithm(){
        for(int step = 0; step < graph.GetNumberOfVertices(); step++){
            int vertex_to_process = graph.GetNumberOfVertices();
            for(int vertex = 0; vertex < graph.GetNumberOfVertices(); vertex++){
                if(!used[vertex] && (distances[vertex] < distances[vertex_to_process])){
                    vertex_to_process = vertex;
                }
            }
            if(distances[vertex_to_process] == INFINITY){
                break;
            }
            PerformRelaxation(vertex_to_process);
        }
    }
    
    
public:
    //хотел навесить const, но компилятор сказал
    //error: invalid initialization of reference of type ‘Graph&’ from expression of type ‘const Graph’
    //я не смог понять, как это лечится
    DijkstraAlgo (Graph& graph, int start_vertex) : 
    graph(graph) //наверняка в этой строчке проблема. Но как ее решить я не знаю.
    ,start_vertex(start_vertex)
    ,parent(graph.GetNumberOfVertices()),
    distances(graph.GetNumberOfVertices(), INFINITY),
    used(graph.GetNumberOfVertices(), false)
    {
        distances[start_vertex] = 0;
        distances.push_back(INFINITY + 1);
        LaunchAlgorithm();
    }
    std::vector<int> GetDistances()const{
        return distances;
    }
    std::vector<int> FindOptimalPath(int end_vertex)const{
        std::vector<int> answer;
        if(distances[end_vertex] == INFINITY){
            return answer;
        }
        answer.push_back(end_vertex);
        int vertex = end_vertex;
        while(vertex != start_vertex){
            vertex = parent[vertex];
            answer.push_back(vertex);
        }
        std::reverse(answer.begin(), answer.end());
        return answer;
    }
};
